package arithmetic;

import java.util.HashMap;
import java.util.Stack;

/**
 * @Author: Jie
 * @Date: 2019/1/14 13:49
 * @Function : 栈
 * push(x) -- 元素 x 入栈
 * pop() -- 移除栈顶元素
 * peek() -- 获取栈顶元素
 * empty() -- 返回栈是否为空
 *
 * leetcode 20
 * 1、有效的括号 是否合法？
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 *
 * 示例 1:
 *
 * 输入: "()"
 * 输出: true
 *
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 */
public class A_02_Stack {


    public static void main(String[] args) {

        String tempBrackets = "()[]{}";
//        boolean isValid = judgeBrackets(tempBrackets);
        boolean isValid = isValid(tempBrackets);
        System.err.println("string valid is "+isValid);
    }

    /**
     * 思路：1、分左右括号。
     * 2、如果是左括号，那么放入栈
     * 3、如果是右括号，和栈顶元素的key对比，如果不匹配 那么false。
     * 4、判断栈 是否为空，不为空 false。因为防止一堆左括号加入。
     *  时间复杂度 O n
     *  空间复杂度 O n
     */
    private static boolean judgeBrackets(String tempBrackets) {
        HashMap<Character,Character> bracketsMap = new HashMap<Character,Character>();
        bracketsMap.put('(',')');
        bracketsMap.put('[',']');
        bracketsMap.put('{','}');
        Stack<Character> mStack = new Stack<>();
        char[] chars = tempBrackets.toCharArray();
        for (char inputChar : chars) {
            if (bracketsMap.containsKey(inputChar)) {
                mStack.push(inputChar);
            } else {
                if (mStack.isEmpty()||bracketsMap.get(mStack.pop()) != inputChar) {
                    System.out.println("not =="+inputChar);
                    return false;
                }
            }
        }

        return mStack.empty();
    }

    /**
     * 如果是【左】括号，那么加入【右】括号，判断下个右括号与【栈顶】是否相等。
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            System.out.println("isEmpty=="+stack.isEmpty());
            if (c == '(')
                stack.push(')');
            else if (c == '{')
                stack.push('}');
            else if (c == '[')
                stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c)//清空
                return false;
        }
        System.out.println("isEmpty=="+stack.isEmpty());
        return stack.isEmpty();
    }
}
